[NOI Online]ring

2020-03-08
#结论
NOI-Online

题意

多次询问给出k，重新排列$\{a_i\}$，使得所有环上距离为$k$的两数的积的和最大

输出最大值，$n,Q\leq 2\cdot 10^5$

题解

大环会被分成$\gcd(n,k)$个小环，且每个环长度均为$\frac{n}{\gcd(n,k)}$

显然大的集中在一个环里面更优，则第$i$个环中的数是$a_{i\cdot L}\dots a_{(i+1)\cdot L-1}$

对于每个小环，一定是42135这样排最优，记忆化一下就好了

调试记录

比赛里面猜出结论没敢用？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <cstdio>
#include <functional>
#include <algorithm>
#define LL long long
using namespace std;
const int maxn = 2e5 + 5;
int n, Q, L, a[maxn];
LL rec[maxn];
int _gcd(int x, int y){
	return (!y) ? x : _gcd(y, x % y);
}
int main(){
	scanf("%d%d", &n, &Q);
	for (int i = 0; i < n; i++) scanf("%d", a + i), rec[0] += 1ll * a[i] * a[i];
	sort(a, a + n, greater<int>());
	for (int k, i = 1; i <= Q; i++){
		scanf("%d", &k);
		if (k == 0){
			printf("%lld\n", rec[0]);
			continue;
		}
		L = n / _gcd(n, k);
		if (rec[L] != 0){
			printf("%lld\n", rec[L]);
			continue;
		}
		for (int i = 0; i < n / L; i++){
			rec[L] += 1ll * a[i * L + 1] * a[i * L] + 1ll * a[(i + 1) * L - 1] * a[(i + 1) * L - 2];
			for (int j = i * L + 1; j + 2 < i * L + L; j += 2)
				rec[L] += 1ll * a[j] * a[j + 2];
			for (int j = i * L; j + 2 < i * L + L; j += 2)
				rec[L] += 1ll * a[j] * a[j + 2];
		} printf("%lld\n", rec[L]);
	}
	return 0;
}